package 华为OD机试B卷复用题.基础题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class HJ49_素数之积 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试B卷复用题/基础题/input/49.txt"));
        MyUtil.START();
        Solution(in);
        MyUtil.END();
    }

    static List<Integer> prime = new ArrayList<>();
    static boolean[] isNotPrime;

    static void Solution(Scanner in) {
        initPrime(1000000);
        System.out.println(prime.toString());
    }

    // 欧拉筛，其它没什么好讲的。
    static void initPrime(int n) {
        isNotPrime = new boolean[n + 1];
        isNotPrime[1] = true;
        for (int i = 2; i <= n; i++) {
            if (!isNotPrime[i]) {
                prime.add(i);
            }
            for (int j = 0; j < prime.size() && prime.get(j) * i <= n; j++) {
                isNotPrime[prime.get(j) * i] = true;
            }
        }
    }
}
